package com.leetcode.algorithm.y22.m08.w2;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 47. 全排列 II
 * 
 * https://leetcode.cn/problems/permutations-ii/
 * 
 * @author jie.deng
 *
 */
class Question0047Solution01 {

	public List<List<Integer>> permuteUnique(int[] nums) {
		List<List<Integer>> result = new ArrayList<>();
		Deque<Integer> path = new ArrayDeque<>();
		boolean[] pathUsed = new boolean[nums.length];
		backtracking(nums, result, path, pathUsed);
		return result;
	}

	private void backtracking(int[] nums, List<List<Integer>> result, Deque<Integer> path, boolean[] pathUsed) {
		int len = nums.length;
		if (path.size() == len) {
			result.add(new ArrayList<>(path));
			return;
		}

		Set<Integer> levelUsed = new HashSet<>();
		for (int i = 0; i < len; i++) {
			if (pathUsed[i]) {
				// 全排列路径不重复（索引不重复）
				continue;
			}

			if (!levelUsed.add(nums[i])) {
				// 相同层不重复(数字不重复)
				continue;
			}
			path.offerLast(nums[i]);
			pathUsed[i] = true;
			backtracking(nums, result, path, pathUsed);

			path.pollLast();
			pathUsed[i] = false;
		}
	}
}